質數對

• Input: 正整數N (N < 10^5)
• Output:計算<=N的質數對個數
  質數對：差值為2的質數一組

第一版，(搞錯題目意思)

以為是將所有差為2的質數排列，取出最長的序列@@

def checkPrime(num):
    i = 2
    while i <= int(num/2):
        if num % (i+1) == 0:
            return False
        i +=1
    return True

iInput = int(input())
lst = []
i = 2

while i <= iInput:
    if i ==2:
        lst.append(i)
    elif i % 2 != 0 :
        if checkPrime(i):
            lst.append(i)
    i +=1

lst_tmp = []
lst_rtn = []
for i in range(len(lst)):
    if i == 0 or lst[i] == lst[i-1] +2 :
        lst_tmp.append(lst[i])
    else:        
        if len(lst_tmp) > len(lst_rtn):
            lst_rtn = lst_tmp
        #print(lst_tmp)
        lst_tmp = [lst[i]]  

print(lst)
print(lst_rtn)
print(len(lst_rtn))

執行

20 #Input
[2]       #list 1
[3, 5, 7] #list 2
[11, 13]  #list 3
[2, 3, 5, 7, 11, 13, 17, 19] #20內的所有質數
[3, 5, 7] #取出最長list
3         #最長的list個數

第二版，(終於搞懂題目意思，但過不了最大測資)

只要差為2的質數即為一對，計算輸入的數字內有幾對質數對
舉例：Input 20，[3 5],[5 7],[11 13],[17 19]，有4對質數對

def checkPrime(num):
    i = 2
    while i <= int(num/2):
        if num % (i+1) == 0:
            return False
        i +=1
    return True

iInput = int(input())
lst = []
i = 2
icount = 0
iIndex = -1

while i <= iInput:
    if i ==2:
        lst.append(i)
        iIndex +=1
    elif i % 2 != 0 :
        if checkPrime(i):
            lst.append(i)
            iIndex +=1
            if iIndex > 0 and lst[iIndex] == lst[iIndex-1] +2 :
                icount+=1
    i +=1
print(icount)

#Input:20
#Answer:4

第三版，修正1(最大測資還是超時)

經高人指點...

• 判斷質數只要計算到開根號(竟然忘了!)
• 判斷質數，+=2遞增，可以略過偶數不用判斷
• 原本是用Empty list再判斷塞資料，-->改成先將list塞進[2,3]，不用判斷list[-1],list[-2]是否存在

def checkPrime(num):
    #進來的數不會有偶數，從5開始+=2
    i = 3
    while i <= int(num ** 0.5):
        if num % i == 0:
            return False
        i +=2 #進來的數不會有偶數，直接用+=2遞增
    return True

iInput = int(input())
lst = [2,3]
i = 5
icount = 0

while i <= iInput:
    if checkPrime(i):
        lst.append(i)
        #先在lst塞好2個值，也不需判斷iIndex > 0
        if lst[-1] == lst[-2] +2 :
            icount+=1
    i +=2 #+=2就不會有偶數可省略判斷偶數
print(icount)

#最大測資Input:99999,Output:1224 673ms  超時

第四版，修正2(最大測資終於過了)

• 只有將判斷質數，從while改寫成for

import datetime

def checkPrime(num):
    #進來的數不會有偶數，從5開始+=2
    for i in range(3,int(num ** 0.5)+1, 2):
        if num % i == 0:
            return False
    '''從while改寫成for
    while i <= int(num ** 0.5):
        if num % i == 0:
            return False
        i +=2 #進來的數不會有偶數，直接用+=2遞增
    '''
    return True

iInput = int(input())
starttime = datetime.datetime.now()
lst = [2,3]
i = 5
icount = 0

while i <= iInput:
    if checkPrime(i):
        lst.append(i)
        #先在lst塞好2個值，也不需判斷iIndex > 0
        if lst[-1] == lst[-2] +2 :
            icount+=1
    i +=2 #+=2就不會有偶數可省略判斷偶數
print(icount)

#After long running
endtime = datetime.datetime.now()
print ('Run time:',(endtime - starttime).microseconds / 1000 ,'ms')

#最大測資99999, 164ms

第五版，修正3(優化把所有while都改成for)

• 把所有while都改成for

import datetime

def checkPrime(num):
    #進來的數不會有偶數，從5開始+=2
    for i in range(3,int(num ** 0.5)+1, 2):
        if num % i == 0:
            return False
    return True

iInput = int(input())
starttime = datetime.datetime.now()
lst = [2,3]
i = 5
icount = 0

for i in range(5,iInput+1,2):
#while i <= iInput: --把while改寫成for
    if checkPrime(i):
        lst.append(i)#
        if lst[-1] == lst[-2] +2 :
            icount+=1
    #i +=2 #+=2就不會有偶數可省略判斷偶數 --把while改寫成for
print(icount)

#After long running
endtime = datetime.datetime.now()
print ('Run time:',(endtime - starttime).microseconds / 1000 ,'ms')

#最大測資99999, 164ms

本文純自己做題目之筆記，如有更好的方法再麻煩各位指教~~